#include <fstream>
#include <set>
#include <iostream>
#include <string>
#include <vector>

struct Card
{
    int id{-1};
    int size{1};
    std::set<int> winningNumbers{};
    std::set<int> numbers{};
};

std::set<int> getNumbers(const std::string& line)
{
    std::set<int> numbers{};
    std::size_t index{0};
    while (index < line.size())
    {
        if (line[index] == ' ')
        {
            index += 1;
            continue;
        }

        // Find next sapce
        std::size_t pos{index + 1};
        while (true)
        {
            if (pos >= line.size() || line[pos] == ' ')
                break;
            pos += 1;
        }

        // line[index, pos) is digit
        numbers.insert(std::stoi(&line[index]));
        index = pos + 1;
    }
    return numbers;
}

std::vector<Card> getCards(const std::string& filename)
{
    std::ifstream file{filename};
    std::string line;
    std::vector<Card> cards{};
    
    while (std::getline(file, line))
    {
        Card card{};
        
        // Card id
        std::size_t pos{line.find_first_of("0123456789")};
        card.id = std::stoi(&line[pos]);

        // Winning numbers
        std::size_t colon{line.find(':')};
        std::size_t separated{line.find('|')};
        card.winningNumbers = getNumbers(line.substr(colon + 1, separated - colon - 1));
        card.numbers = getNumbers(line.substr(separated + 1, line.size() - separated - 1));

        cards.emplace_back(std::move(card));
    }

    return cards;
}

// =================== Part1 =================== //

int getPoints(const std::vector<Card>& cards)
{
    int sum{0};
    auto pow = [] (int e) -> int {
        int value = 1;
        while (--e)
            value *= 2;
        return value;
    };

    for (const Card& card : cards)
    {
        int size{0};
        for (int n : card.numbers)
        {
            if (card.winningNumbers.find(n) != card.winningNumbers.end())
                size += 1;
        }
        if (size > 0)
            sum += pow(size);
    }
    return sum;
}

// =================== Part2 =================== //
int getScratchcardsSize(std::vector<Card>& cards)
{
    int scratchcardsSize{0};
    for (std::size_t i = 0; i < cards.size(); ++i)
    {
        scratchcardsSize += cards[i].size;
        
        // Get this card's hit size
        int hitSize{0};
        for (int n : cards[i].numbers)
        {
            if (cards[i].winningNumbers.find(n) != cards[i].winningNumbers.end())
                hitSize += 1;
        }

        // Get copy card
        for (int j = i + 1; j <= i + hitSize; ++j)
        {
            if (j < cards.size())
                cards[j].size += cards[i].size;
        }
    }

    return scratchcardsSize;
}

int main()
{
    std::vector<Card> cards{getCards("./src/day04/input.txt")};
    // for (const Card& card : cards)
    // {
    //     std::cout << "Card " << card.id << ": ";

    //     std::cout << "[ ";
    //     for (int n : card.winningNumbers)
    //         std::cout << n << ' ';
    //     std::cout <<  "] | [ ";
    //     for (int n : card.numbers)
    //         std::cout << n << ' ';
    //     std::cout << "]\n";
    // }
    // std::cout << getPoints(cards) << std::endl;
    std::cout << getScratchcardsSize(cards) << std::endl;

    return 0;    
}